package com.milo.algorithm.sort;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

/**
 * @author: Milogenius
 * @create: 2019-07-04 17:33
 * @description: 插入排序
 **/
public class InsertSort {

    public int[] sort(int[] sourceArray){
        //对array进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //从下标为i的元素开始选择合适的位置插入,因为下标为0的元素只有一个,默认是有序的
        for (int i = 1; i < arr.length; i++) {
            //记录要插入的数据
            int tmp = arr[i];
            //从已经排序的序列的最右边开始比较,找到比其小的数
            int j = i;
            while (j>0 && tmp<arr[j-1] ) {
                arr[j] = arr[j - 1];
                j--;
            }
            //存在比其小的数,插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,44,38,5,47};
        InsertSort insertSort = new InsertSort();
        int[] sort = insertSort.sort(arr);
        System.out.println("排序后的数组顺序:"+ JSON.toJSONString(sort));
    }
}
